#include<iostream>

using namespace std;

template<typename T>
class dlist {
public:
	struct Node {
		Node* next = nullptr;
		Node* pre = nullptr;
		T val;
		Node():val(){};
		Node(T v) :val(v) {};
		Node(Node* pe, T v) :pre(pe), val(v) {};
		Node(Node* pr, Node* ne, T v) :pre(pr), next(ne), val(v) {};
	};
	class iter {
	public:
		Node *p;
		iter(Node* ptr=nullptr) :p(ptr) {};
		T& operator*() { return p->val; };
		iter& operator++() { p = p->next; return *this; };//前置
		iter operator++(int) { iter old = *this; p = p->next; return old; };
		iter& operator--() { p = p->pre; return *this; };//前置
		iter operator--(int) { iter old = *this; p = p->pre; return old; };//后置
		Node* operator->() { return p; }
		bool operator==(const iter& r)const { return p == r.p; };
		bool operator!=(const iter& r)const { return p != r.p; };
	};

public:
	dlist() :head(new Node()), vsize(0), tail(head) {};
	dlist(unsigned n, const T& t);
	dlist(const dlist&);
	dlist& operator=(dlist a);
	~dlist();
	bool empty() { return vsize == 0; };
	unsigned size()const { return vsize; };
	iter begin()const { return iter(head->next); };
	iter end()const { return iter(tail->next); };
	void insert(iter p, const T&);
	void push_back(const T& v);
	void push_front(const T& v);
	void erease(iter p);
	void print();
	void pop_back();
	void pop_front();
	iter find(const T& v) {
		Node* temp = head->next;
		while (temp != nullptr && temp->val != v)
			temp = temp->next;
		return iter(temp);
	};
	T& back() { return tail->val; };
	T& front() { return head->next->val; };
private:
	unsigned int vsize;
	Node* head;//不储存数据
	Node* tail;
};

template<typename T>
dlist<T>::dlist(unsigned n, const T& t):dlist()
{
	for (int i = 0; i < n; ++i) push_back(t);
}
template<typename T>
dlist<T>::~dlist()
{
	while (head) {
		Node* p = head;
		head = head->next;
		delete p;
	}
}

template<typename T>
void dlist<T>::push_back(const T& v){
	tail->next = new Node(tail, v);
	tail = tail->next;
	vsize++;
}

template<typename T>
dlist<T>::dlist(const dlist& t)
{
	head =tail= new Node();
	Node* p = t.head->next;
	while (p) {
		this->push_back(p->val);
		p = p->next;
	}
}

template<typename T>
void dlist<T>::insert(iter pt, const T& x)
{
	vsize++;
	Node* p = pt.p;
	Node* temp = new Node(p, p->next, x);
	if (p == tail) tail = temp;
	p->next->pre = temp;
	p->next = temp;
}
template<typename T>
void dlist<T>::push_front(const T& v){
	head->next = new Node(head, head->next, v);
	head->next->next->pre = head->next;
	if (vsize == 0) tail = head->next;
	vsize++;
}


template<typename T>
void dlist<T>::erease(iter i)
{
	Node* temp = i.p;
	if (temp == tail) { tail = tail->pre; };
	if (temp->pre == head) cout << "cao ";
	temp->pre->next = temp->next;//bug

	if(temp->next!=nullptr)
	temp->next->pre = temp->pre;
	
		delete temp;
		vsize--;
}

template<typename T>
void dlist<T>::print()
{
	Node* p = head->next;
	while (p) {
		cout << p->val<<" ";
		p = p->next;
	}
	cout << endl;
}



template<typename T>
dlist<T>& dlist<T>::operator=(dlist a)
{
	swap(a.head, head);
	swap(a.vsize, vsize);
	swap(a.tail, tail);
}

template<typename T>
void dlist<T>::pop_back(){
	if (vsize == 0) return;
	vsize--;
	tail = tail->pre;
	delete tail->next;
	tail->next = nullptr;
}

template<typename T>
void dlist<T>::pop_front()
{
	if (vsize == 0) return ;
	if (vsize == 1) tail = head;
	vsize--;
	Node* temp = head->next;
	head->next = temp->next;
	delete temp;
	if (vsize != 0) head->next->pre = head;
}

int main()
{
	dlist<int> test;
	for(int i=0;i<5;++i)
	test.push_back(i);
	for (auto i = test.begin(); i != test.end(); ++i)//测试迭代器
		cout << *i << " ";
	cout << endl;
	 auto it = test.find(2);
	test.erease(it);
	test.print();
	dlist<int> test1(test);//复制构造函数
	for (int i = 0; i < 5; ++i)
		test1.push_front(-i);
	test1.print();

	dlist<int>::iter itt = test1.find(0);
	test1.erease(itt);//删除0
	cout << endl;
	test1.insert(test1.begin(), 100);
	test1.print();
	cout << "size" << test1.size();
}


